package test9;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Demo3 {
    public static void main(String[] args) {
        int[][] matrix = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}};
        for (int i = 0; i < matrix.length; i++) {
            System.out.println(Arrays.toString(matrix[i]));
        }
        System.out.println(spiralOrder(matrix));
    }

    static List<Integer> res = new ArrayList<>();
    static int height;
    static int width;
    static int[][] dp;

    public static List<Integer> spiralOrder(int[][] matrix) {
        height = matrix.length;
        width = matrix[0].length;
        dp = new int[height][width];
        traverse(matrix, 0, 0, 0);
        return res;
    }

    static void traverse(int[][] matrix, int i, int j, int direct) {
        res.add(matrix[i][j]);
        dp[i][j] = 1;
        //坚持上一次走的方向，走不通按照 右， 下， 上， 左 寻找
        if (direct == 0) {
            if (j + 1 < width && dp[i][j + 1] == 0) {
                traverse(matrix, i, j + 1, 0);
            } else {
                findDirect(matrix, i, j);
            }
        } else if (direct == 1) {
            if (i + 1 < height && dp[i + 1][j] == 0) {
                traverse(matrix, i + 1, j, 1);
            } else {
                findDirect(matrix, i, j);
            }
        } else if (direct == 2) {
            if (j - 1 >= 0 && dp[i][j - 1] == 0) {
                traverse(matrix, i, j - 1, 2);
            } else {
                findDirect(matrix, i, j);
            }
        } else {
            if (i - 1 >= 0 && dp[i - 1][j] == 0) {
                traverse(matrix, i - 1, j, 3);
            } else {
                findDirect(matrix, i, j);
            }
        }
    }


    public static void findDirect(int[][] matrix, int i, int j) {
        //右 0
        if (j + 1 < width && dp[i][j + 1] == 0) {
            traverse(matrix, i, j + 1, 0);
            //下 1
        } else if (i + 1 < height && dp[i + 1][j] == 0) {
            traverse(matrix, i + 1, j, 1);
            //上 2
        } else if (j - 1 >= 0 && dp[i][j - 1] == 0) {
            traverse(matrix, i, j - 1, 2);
            //左 3
        } else if (i - 1 >= 0 && dp[i - 1][j] == 0) {
            traverse(matrix, i - 1, j, 3);
        }
    }
}
